[题解]LG4310 绝世好题

https://www.luogu.com.cn/problem/P4310

题目描述

给定 $a_{1…n}$，求 $a_i$ 子序列 $b_i$ 最长长度满足 $b_i\&b_{i-1}\neq 0$。

$1\le n\le 100000$。

题解

80分算法 $f(i)$ 表示前 $i$ 个且选 $i$ 的最长长度，随便 DP 即可。

100分算法 考虑分位DP，$f(i)$ 表示第 $i$ 位不为 $0$ 的最长长度，动态更新。

#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
using namespace std;

int n,f[39],ans;

int main() {
	scanf("%d",&n);
	rep(i,1,n) {
		int x; scanf("%d",&x);
		int mx=0;
		rep(i,0,30) if((1<<i)&x) mx=max(mx,f[i]+1);
		rep(i,0,30) if((1<<i)&x) f[i]=max(f[i],mx);
		rep(i,0,30) ans=max(ans,f[i]);
	}
	printf("%d\n",ans);
	return 0;
}